package main;

import java.util.List;

/**
 * @author zhx
 * @since 2020-07-14
 * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
 * <p>
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * <p>
 *  
 * <p>
 * 例如，给定三角形：
 * <p>
 * [
 * [2],
 * [3,4],
 * [6,5,7],
 * [4,1,8,3]
 * ]
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/triangle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode30 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int length = triangle.size();
        int[][] dp = new int[2][length];
        dp[0][0] = triangle.get(0).get(0);
//        index++;
        for (int i = 1; i < length; i++) {
            dp[i % 2][0] = triangle.get(i).get(0) + dp[(i - 1) % 2][0];
            for (int j = 1; j < i; j++) {
                dp[i % 2][j] = triangle.get(i).get(j) + Math.min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - 1]);
            }
            dp[i % 2][i] = triangle.get(i).get(i) + dp[(i - 1) % 2][i - 1];

        }
        int min = dp[(length - 1) % 2][0];
        for (int i = 1; i < length; i++) {
            min = Math.min(min, dp[(length - 1) % 2][i]);
        }
        return min;
    }
}
